package com.jake.data_structure_learning.solution;

import java.util.Stack;

/**
 * copyright (C), 2021, 武汉德辞信息技术有限公司
 *
 * @author WangXiang
 * @version 1.0.0
 * @create 2021/6/24 14:24
 * @description <author>                <time>                  <version>
 * WangXiang               2021/6/24 14:24            1.0.0
 */
public class Solution {
    /**
     * 输入: x = 1, y = 4
     * <p>
     * 输出: 2
     * <p>
     * 解释:
     * 1   (0 0 0 1)
     * 4   (0 1 0 0)
     * ↑   ↑
     * <p>
     * 上面的箭头指出了对应二进制位不同的位置。
     *
     * @param x
     * @param y
     * @return
     */
    public static int hammingDistance(int x, int y) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            int a = x >> i & 1;
            int b = y >> i & 1;
            if (a != b) {
                count++;
            }
        }
        return count;
    }

    /**
     * 反转二进制位
     *
     * @param x
     * @return
     */
    public static int reverseBit(int x) {
        int reverseX = 0;

        for (int i = 0; i < 32; i++) {
            int bit = (x >> i) & 1;
            reverseX = reverseX + (bit << (31 - i));
        }
        return reverseX;
    }

    /**
     * 给定一个整数数组 n u m s ，其中恰好有两个元素只出现一次，其余所有元素均出现两
     * 次。找出只出现一次的那两个元素。
     * 示例 :
     * 输入: [ 1 , 2 , 1 , 3 , 2 , 5 ]
     * 输出: [ 3 , 5 ]
     */
    public int[] singleNumber(int[] nums) {
        int record = 0;
        for (int i = 0; i < nums.length; i++) {
            record = record ^ nums[i];
        }
        return new int[]{record};
    }

    /**
     * 给定两个字符串s和t，它们只包含小写字母。
     * 字符串t由字符串s随机重排，然后在随机位置添加一个字母。
     * 请找出在t中被添加的字母。
     * 示例 1：
     * 输入：s = " a b c d " , t = " a b c d e "
     * 输出：" e "
     * 解释：' e ' 是那个被添加的字母。
     * 示例 2：
     * 输入：s = " " , t = " y "
     * 输出：" y "
     * 原创 山大王wld 数据结构和算法 1周前示例 3：
     * 输入：s = " a " , t = " a a "
     * 输出：" a "
     * 示例 4：
     * 输入：s = " a e " , t = " a e a "
     * 输出：" a "
     */
    public static char findTheDifference(String s, String t) {
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        int c = 0;
        for (int i = 0; i < a.length; i++) {
            c = c ^ a[i];
        }
        for (int i = 0; i < b.length; i++) {
            c = c ^ b[i];
        }
        return (char) c;
    }

    /**
     * 给 你 一 个 整 数 数 组 arr 。 请 你 将 数 组 中 的 元 素 按 照 其 二 进 制 表 示 中 数 字 1 的 数 目 升 序 排
     * 序。
     * 如果存在多个数字二进制中1的数目相同，则必须将它们按照数值大小升序排列。
     * 请你返回排序后的数组。
     * 示例 1：
     * 输入：a r r = [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]
     * 输出：[ 0 , 1 , 2 , 4 , 8 , 3 , 5 , 6 , 7 ]
     * 解释：[ 0 ] 是唯一一个有 0 个 1 的数。
     * [ 1 , 2 , 4 , 8 ] 都有 1 个 1 。
     * [ 3 , 5 , 6 ] 有 2 个 1 。
     * [ 7 ] 有 3 个 1 。
     * 原创 山大王wld 数据结构和算法 11月13日按照 1 的个数排序得到的结果数组为 [ 0 , 1 , 2 , 4 , 8 , 3 , 5 , 6 , 7 ]
     * 示例 2：
     * 输入：a r r =
     * [ 1 0 2 4 , 5 1 2 , 2 5 6 , 1 2 8 , 6 4 , 3 2 , 1 6 , 8 , 4 , 2 , 1 ]
     * 输出：
     * [ 1 , 2 , 4 , 8 , 1 6 , 3 2 , 6 4 , 1 2 8 , 2 5 6 , 5 1 2 , 1 0 2 4 ]
     * 解释： 数 组 中 所 有 整 数 二 进 制 下 都 只 有 1 个 1 ， 所 以 你 需 要 按 照 数 值 大 小 将 它 们 排
     * 序。
     * 示例 3：
     * 输入：a r r = [ 1 0 0 0 0 , 1 0 0 0 0 ]
     * 输出：[ 1 0 0 0 0 , 1 0 0 0 0 ]
     * 示例 4：
     * 输入：a r r = [ 2 , 3 , 5 , 7 , 11 , 1 3 , 1 7 , 1 9 ]
     * 输出：[ 2 , 3 , 5 , 1 7 , 7 , 11 , 1 3 , 1 9 ]
     * 示例 5：
     * 输入：a r r = [ 1 0 , 1 0 0 , 1 0 0 0 , 1 0 0 0 0 ]
     * 输出：[ 1 0 , 1 0 0 , 1 0 0 0 0 , 1 0 0 0 ]
     * 提示：
     * 1 <= arr.length <= 500
     * 0 <= arr[i] <= 10^4
     */

    public static int[] sortByBits(int[] arr) {
        return null;
    }

    /**
     * 给一个函数f(x)，返回一个不小于x的最小的2的n次方。描述的比较绕口，举个例子。
     * f ( 7 ) = 8
     * f ( 9 ) = 1 6
     * f ( 3 0 ) = 3 2
     * f ( 6 4 ) = 6 4
     * 注意：
     * x是正整数
     * 0<x<Integer.MAX_VALUE
     */


    public String removeDuplicate(String s) {
        return "";
    }

    /**
     * 中缀转后缀
     * 1.从左到右扫描每一个字符。如果扫描到的字符是操作数（如a、b等），就直接输出这些操作数。
     * a + b * c + ( d * e + f ) * g
     * 2.如果扫描到的字符是一个操作符，分三种情况：
     * <p>
     * （1）如果堆栈是空的，直接将操作符存储到堆栈中（push it）
     * <p>
     * （2）如果该操作符的优先级大于堆栈出口的操作符，就直接将操作符存储到堆栈中（push it）
     * <p>
     * （3）如果该操作符的优先级低于堆栈出口的操作符，就将堆栈出口的操作符导出（pop it）, 直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中（push）。
     *
     * @param mid
     * @return
     */
    public Stack<Character> changeMidToEnd(String mid) {
        Stack<Character> opera = new Stack<>();
        Stack<Character> nums = new Stack<>();
        for (int i = 0; i < mid.length(); i++) {
            if (mid.charAt(i) == '+') {

            } else if (mid.charAt(i) == '-') {

            } else if (mid.charAt(i) == '*') {

            } else if (mid.charAt(i) == '/') {

            } else if (mid.charAt(i) == '+') {

            } else if (mid.charAt(i) == '(') {

            } else if (mid.charAt(i) == ')') {

            } else {
                nums.push(mid.charAt(i));
            }
        }
        return nums;
    }

    /**
     * 给定两个数组，编写一个函数来计算它们的交集。
     * 输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
     * 我们可以不考虑输出结果的顺序
     * [1,2,3,4] [3,4]
     */
//    public int[] intersect(int[] nums1, int[] nums2) {
//
//    }
}
